package com.cg.leetcode;

import org.junit.Test;

/**
 * 189.旋转数组
 *
 * @program: LeetCode->LeetCode_189
 * @description: 189.旋转数组
 * @author: cg
 * @create: 2021-08-31 15:46
 **/
public class LeetCode_189 {

    @Test
    public void test189() {
        rotate(new int[]{1, 2, 3, 4, 5, 6, 7}, 3);
    }

    /**
     * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
     *  
     * 进阶：
     * 1) 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
     * 2) 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
     * <p>
     * 示例 1:
     * 输入: nums = [1,2,3,4,5,6,7], k = 3
     * 输出: [5,6,7,1,2,3,4]
     * 解释:
     * 向右旋转 1 步: [7,1,2,3,4,5,6]
     * 向右旋转 2 步: [6,7,1,2,3,4,5]
     * 向右旋转 3 步: [5,6,7,1,2,3,4]
     * <p>
     * 示例 2:
     * 输入：nums = [-1,-100,3,99], k = 2
     * 输出：[3,99,-1,-100]
     * 解释:
     * 向右旋转 1 步: [99,-1,-100,3]
     * 向右旋转 2 步: [3,99,-1,-100]
     * <p>
     * 提示：
     * 1) 1 <= nums.length <= 2 * 10的4次幂
     * 2) -2的31次幂 <= nums[i] <= 2的31次幂 - 1
     * 3) 0 <= k <= 10的5次幂
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        //多次反转解决
        int length = nums.length;
        k %= length;
        //先反转全部的元素
        reverse(nums, 0, length - 1);
        //在反转前k个元素
        reverse(nums, 0, k - 1);
        //接着反转剩余的
        reverse(nums, k, length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        //把数组中从[start，end]之间的元素两两交换,也就是反转
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }
    /*public void rotate(int[] nums, int k) {
        //使用临时数组解决
        int length = nums.length;
        int[] temp = new int[length];
        //把原数组值放到一个临时数组中，
        System.arraycopy(nums, 0, temp, 0, length);
        //然后在把临时数组的值重新放到原数组，并且往右移动k位
        for (int i = 0; i < length; i++) {
            nums[(i + k) % length] = temp[i];
        }
    }*/

}
